package org.byteDance.l322;

/**
 * @Author yu
 * @Date 2022/3/8
 */
public class Solution {

    public static void main(String[] args) {

        int[] ints = {1, 2, 5};

        Solution solution = new Solution();
        System.out.println(solution.coinChange(ints, 11));

    }

    public int coinChange(int[] coins, int amount) {
        if (coins.length == 0) {
            return 0;
        }

        // 用数组记录 amount + 1 范围内每一个金额所需最少硬币个数，+ 1 为确保金额 amount 可以被计算
        int[] ints = new int[amount + 1];

        // 0 元需要 0 个硬币
        ints[0] = 0;

        for (int i = 1; i <= amount; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < coins.length; j++) {

                // dp[11] = dp[10] + dp[1]，dp[10] = dp[9] + dp[1]，dp[10] = dp[8] + dp[2]
                if (i - coins[j] >= 0 && ints[i - coins[j]] < min) {
                    min = ints[i - coins[j]] + 1;
                }
            }
            ints[i] = min;
        }

        return ints[amount] == Integer.MAX_VALUE ? -1 : ints[amount];
    }

}
